//
//  BinaryTree.h
//  leetcode
//
//  Created by Ellie on 2021/1/27.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef BinaryTree_h
#define BinaryTree_h

#include "DataDefine.h"
#include <queue>
#include <unordered_map>
#include <string>
#include <stack>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

// Binary Serach Tree

class BinaryTreeBST
{
public:
    // Binary Serach Tree Method
    TreeNode* insertnode(TreeNode* root, int value);
    TreeNode* findnode(TreeNode* root, int value);
    TreeNode* deletenode(TreeNode* root, int value);
    TreeNode* getmin(TreeNode* root);
    TreeNode* getmax(TreeNode* root);
    TreeNode* deletemin(TreeNode* root);
    TreeNode* deletemax(TreeNode* root);
    
    vector<TreeNode*> splitBST(TreeNode* root, int V);
    
    // 101. 对称二叉树 isSymmetric
    bool isSymmetric(TreeNode* left, TreeNode* right);
    bool isSymmetricInteration(TreeNode* left, TreeNode* right);
    // Is Same Tree
    bool isSameTree(TreeNode* root1, TreeNode* root2);
    // Is Sub Tree
    bool isSubTree(TreeNode* root, TreeNode* target);
    // Is BST
    bool isBST(TreeNode* root);
    // Is Balanced
    bool isBalanced(TreeNode* root);
    // pre-order,in-order,post-order,level-order,之字order,right slideview
    // DFS 递归和迭代写法
    void preOrder(TreeNode* root, vector<int>& result);
    void inOrder(TreeNode* root, vector<int>& result);
    void postOrder(TreeNode* root, vector<int>& result);
    // BFS queue DFS
    void levelOrder(TreeNode* root, vector<int>& result);
    // DFS or BFS
    void levelTwoOrder(TreeNode* root, vector<int>& result);
    // DFS or BFS
    void rightslideViewOrder(TreeNode* root, vector<int>& result);
    
    void getAllPath(TreeNode* root, vector<vector<int>>& result);
    
    // 针对二叉树的操作，反转二叉树，上下翻转二叉树
    // 156. 上下翻转二叉树 题目不是很好理解，left->left = node->right,left->right = node ; node->left = node->right = nullptr
    TreeNode* upsideDownBinaryTree(TreeNode* root);
    
    // 二叉树的构建算法
    TreeNode* buildTreeWithPreInOrder(vector<int> preorder, vector<int> inorder);
    TreeNode* buildTreeWithPostInOrder(vector<int> input, vector<int> inorder);
    
    // 109. 有序链表转换二叉搜索树，有序数组转化为平衡的二叉搜索树
    TreeNode* sortedListToBST(ListNode* head);
    TreeNode* buildBSTHelper(ListNode* left, ListNode* right);
    
    // DFS and BFS
    int minDepth(TreeNode* root);
    // same to get height
    int maxDepth(TreeNode* root);
    
    // 1028. Recover a Tree From Preorder Traversal
    // 前序遍历加上level信息，二叉树的右视图，新的level发生变化就是该层的最右侧或者左侧的元素
    TreeNode* recoverFromPreorder(string str);
    
    // 二叉树的序列化
    // 297. 二叉树的序列化与反序列化 MEDIUM
    string serialize(TreeNode* root);
    TreeNode* deserialize(string data);
    TreeNode* deserializeHelper(stringstream& ss);
    
    // 面试题 04.09. 二叉搜索树序列 HARD
    vector<vector<int>> BSTSequences(TreeNode* root);
    void doBSTSequences(vector<vector<int>>& result, deque<TreeNode*> &que, vector<int>& path);
    
    // 129. 求根到叶子节点数字之和 Medium
    // 每个节点表示十进制的一个数字0-9，一个路径表示一个十进制数字
    int sumNumbers(TreeNode* root, int sum);
    // 113. 路径总和 II 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 Medium
    void pathSum(TreeNode* root, int targetSum, vector<vector<int>> &result);
    // 666. 路径和 IV，转化为二叉树，然后求解，满二叉树的性质，使用数组存储i的子节点位2i和2i+1 Medium
    // BFS层序遍历求解，或者DFS求解
    int pathSum(vector<int>& nums);
    // 437. 路径总和 III 所有的路径，将每个节点都作为根节点做一次处理，所有的可能性，遇到sum=0不能返回，应该继续往下找，因为有负数 Medium
    int pathSum(TreeNode* root, int sum);
    void pathSumRecursion(TreeNode* root, int sum);
    void inorderPathSum(TreeNode* root, int sum);
    // 687. 最长同值路径 Hard 124和687有相同的思路，后续遍历，将计算结果保存，同时将满足条件的路径返回
    // right+root，left+root，root，三种情况
    int longestUnivaluePath(TreeNode* root);
    int longestUnivaluePathRecursion(TreeNode* root);
    // 124. 二叉树中的最大路径和 Hard，遍历过程求解，然后将符合条件的返回值给返回
    int maxPathSum(TreeNode* root);
    int maxPathSumPostOrder(TreeNode* root);
    // 222. 完全二叉树的节点个数LogN * LogN
    int countNodes(TreeNode* root);
    // 剑指 Offer 33. 二叉搜索树的后序遍历序列
    // 二叉搜索树的性质，LEFT，RIGHT，ROOT = 后续遍历，找到左右子树
    // ROOT，LEFT，RIGHT = 前序遍历
    // LEFT，ROOT，RIGHT = 中序遍历
    // 找到Left子树然后和RootValue比较，必须所有的值都小于RootValue
    bool verifyPostorder(vector<int>& postorder);
    // 543. 二叉树的直径
    int diameterOfBinaryTree(TreeNode* root);
    int diameterOfBinaryTreeRecursion(TreeNode* root);

private:
    string SEP = " ";
    string NULLNode = "null";
    vector<int> cachePath;
    int cacheIntResult = 0;
};

#endif /* BinaryTree_h */
